1. Field of the Invention
The present invention relates to a digital integrated circuit for performing an arithmetic operation, particularly, an adder, and more particularly to an adder with optimized design costs.
2. Description of the Related Art
A binary adding operation, which is most frequently used in digital systems, plays an essential role in designing general-purpose processors, special-purpose processors such as digital signal processors, and almost all application-specific integrated circuits (ASIC). Moreover, since an adder, which is a basic element for performing large-scale, complicated operations, such as multiplication, division, and floating-point operations, is used in various design units such as a memory address generator or a program counter, it is an important design issue to develop binary adders with optimal design costs.
Numerous studies on various kinds of carry propagation schemes, which are a main design factor of the digital system, taking into consideration operation speed of circuits, amount of silicon used, and power consumption according to design goals, have been conducted. Until high performance adders were developed, early digital systems used a ripple carry adder of the simplest form. FIG. 1 is a block diagram of the ripple carry adder. Equations 1 and 2 are equations for signals si and ci using signal bits xi and yi shown in FIG. 1.si=xi·yi·ci′+xi′·yi·ci′+xi′·yi′·ci+xi·yi·ci  Equation 1ci=xi·yi+xi·ci+yi·ci  Equation 2
In the above equations, a symbol ‘+’ represents a binary OR operation, and a symbol ‘·’ represents a binary AND operation. A symbol ‘′’ is a unary operator for performing a binary NOT operation. Although the ripple carry adder can perform an add operation using a small quantity of silicon, it is very slow in performing the add operation since carry propagation in the adder is linear.
For a higher speed adder, there are many cases where a carry prediction circuit is used to accelerate carry generation and propagation, or a carry propagation path for faster carry propagation is implemented with a multi-layered binary tree structure. A high speed adder commonly used includes a carry skip adder, a carry select adder, a carry lookahead adder, etc. In such adders, the amount of silicon circuits used has been increased in correspondence with increased speed of the add operation.
When an adder is implemented with a multi-layered structure, various carry propagation schemes are applicable to different layers. As suggested in “Carry-Lookahead/Carry-Select Binary Adder, U.S. Pat. No. 5,508,952, Apr. 16, 1996” and “Adder Which Employs Both Carry Look-Ahead and Carry Select Techniques, U.S. Pat. No. 5,898,596 Apr. 27, 1999”, a mixed-type adder, which includes a carry generation layer employing a carry lookahead scheme for high speed carry propagation and a sum generation layer employing a carry select scheme for calculating a sum quickly through carry prediction, has been used for high speed add operations. FIG. 2 is a diagram illustrating a structure of a mixed-type adder employing both the carry lookahead scheme and the carry select scheme.
In conventional adder designs, a single carry propagation scheme has been mainly used, and many different optimization techniques including an optimization at a transistor level, application of an asynchronous design scheme, an optimization of a bit width employing the carry prediction scheme, etc., have been applied to adders employing the signal carry propagation scheme. However, as a mixed-type adder employing a multi carry propagation scheme, there is merely an adder employing only two schemes, the carry prediction scheme and the carry select scheme, applied to different layers. Such a design scheme is restricted in its application range in that the number of combinable carry propagation schemes is few and an applicable adder must have a multi-layered structure.
In FIG. 3, solid lines represent trade-off design spaces for a relationship of delay time-amount of used circuits of an adder, which is attained when a conventional adder structure is used. Delay time-amount of used circuits curves showing trade-off characteristics are formed depending on the kind of adder, and curvatures of the delay time-amount of used circuit curves can be determined by a degree of optimization applied to each adder. Each of delay time-amount of used circuits curves has an ideal banana-shaped inverse-proportional plot. However, when trade-off characteristics for the adder design with no restriction on a particular adder structure are calculated, the delay time-amount of used circuits curves do not have the ideal banana-shaped inverse-proportional plot if each of the delay time-amount of used circuit curves forms a single delay time-amount of used circuit curve.
The delay time-amount of used circuit curves have a non-ideal stepped trade-off curve from an overall point of view. Since the delay time and the amount of used circuits do not have an accurate inverse-proportional relationship in such a non-ideal trade-off curve, even when restrictions on the delay time of adder are alleviated, the amount of used circuits cannot be reduced, which results in ineffective optimization of the adder design. Accordingly, there is a need for a method for obtaining an ideal and effective trade-off curve, as indicated by a dotted line in FIG. 3, in optimization of the relationship of the delay time and the amount of used circuits.